Billiard Ball Computer on:
[Wikipedia]
[Google]
[Amazon]
A billiard-ball computer, a type of conservative logic circuit, is an idealized model of a reversible
A billiard-ball computer, a type of conservative logic circuit, is an idealized model of a reversible mechanical computer
A mechanical computer is a computer built from mechanical components such as levers and gears rather than electronic components. The most common examples are adding machines and mechanical counters, which use the turning of gears to increment out ...
based on Newtonian dynamics
In physics, Newtonian dynamics (also known as Newtonian mechanics) is the study of the dynamics of a particle or a small body according to Newton's laws of motion.
Mathematical generalizations
Typically, the Newtonian dynamics occurs in a thre ...
, proposed in 1982 by Edward Fredkin
Edward Fredkin (born October 2, 1934) is a distinguished career professor at Carnegie Mellon University (CMU), and an early pioneer of digital physics.
Fredkin's primary contributions include work on reversible computing and cellular automata. ...
and Tommaso Toffoli
Tommaso Toffoli () is an Italian-American professor of electrical and computer engineering at Boston University where he joined the faculty in 1995. He has worked on cellular automata and the theory of artificial life (with Edward Fredkin and oth ...
. Instead of using electronic signals like a conventional computer, it relies on the motion of spherical billiard ball
A billiard ball is a small, hard ball used in cue sports, such as carom billiards, pool, and snooker. The number, type, diameter, color, and pattern of the balls differ depending upon the specific game being played. Various particular ball p ...
s in a friction-free environment made of buffers against which the balls bounce perfectly. It was devised to investigate the relation between computation and reversible processes in physics.
Simulating circuits with billiard balls
This model can be used to simulateBoolean circuit
In computational complexity theory and circuit complexity, a Boolean circuit is a mathematical model for combinational digital logic circuits. A formal language can be decided by a family of Boolean circuits, one circuit for each possible inp ...
s in which the wires of the circuit correspond to paths on which one of the balls may travel, the signal on a wire is encoded by the presence or absence of a ball on that path, and the gates of the circuit are simulated by collisions of balls at points where their paths cross. In particular, it is possible to set up the paths of the balls and the buffers around them to form a reversible Toffoli gate
In logic circuits, the Toffoli gate (also CCNOT gate), invented by Tommaso Toffoli, is a universal reversible logic gate, which means that any classical reversible circuit can be constructed from Toffoli gates. It is also known as the "control ...
, from which any other Boolean logic gate may be simulated. Therefore, suitably configured billiard-ball computers may be used to perform any computational task.
Simulating billiard balls in other models of computation
It is possible to simulate billiard-ball computers on several types ofreversible cellular automaton
A reversible cellular automaton is a cellular automaton in which every configuration has a unique predecessor. That is, it is a regular grid of cells, each containing a state drawn from a finite set of states, with a rule for updating all cells s ...
, including block cellular automata and second-order cellular automata. In these simulations, the balls are only allowed to move at a constant speed in an axis-parallel direction, assumptions that in any case were already present in the use of the billiard ball model to simulate logic circuits. Both the balls and the buffers are simulated by certain patterns of live cells, and the field across which the balls move is simulated by regions of dead cells, in these cellular automaton simulations.
Logic gates based on billiard-ball computer designs have also been made to operate using live soldier crabs of the species '' Mictyris guinotae'' in place of the billiard balls..
See also
*Unconventional computing
Unconventional computing is computing by any of a wide range of new or unusual methods. It is also known as alternative computing.
The term ''unconventional computation'' was coined by Cristian S. Calude and John Casti and used at the First In ...
* Fluidics
Fluidics, or fluidic logic, is the use of a fluid to perform analog or digital operations similar to those performed with electronics.
The physical basis of fluidics is pneumatics and hydraulics, based on the theoretical foundation of fluid dyna ...
References
{{reflist Models of computation Mechanical computers Reversible computing